@article{Bennett1973, author = {Bennett, C. H.}, title = {Logical Reversibility of Computation}, journal = {IBM J. Res. Dev.}, issue_date = {November 1973}, volume = {17}, number = {6}, month = nov, year = {1973}, issn = {0018-8646}, pages = {525--532}, numpages = {8}, url = {http://dx.doi.org/10.1147/rd.176.0525}, doi = {10.1147/rd.176.0525}, acmid = {1664568}, publisher = {IBM Corp.}, address = {Riverton, NJ, USA}, } @article{Bennett1982, title={The thermodynamics of computation—a review}, author={Bennett, Charles H}, journal={International Journal of Theoretical Physics}, volume={21}, number={12}, pages={905--940}, year={1982}, publisher={Springer} } @Article{Fredkin1982, author="Fredkin, Edward and Toffoli, Tommaso", title="Conservative logic", journal="International Journal of Theoretical Physics", year="1982", month="Apr", day="01", volume="21", number="3", pages="219--253", abstract="Conservative logic is a comprehensive model of computation which explicitly reflects a number of fundamental principles of physics, such as the reversibility of the dynamical laws and the conservation of certainadditive quantities (among which energy plays a distinguished role). Because it more closely mirrors physics than traditional models of computation, conservative logic is in a better position to provide indications concerning the realization of high-performance computing systems, i.e., of systems that make very efficient use of the ``computing resources'' actually offered by nature. In particular, conservative logic shows that it is ideally possible to build sequential circuits with zero internal power dissipation. After establishing a general framework, we discuss two specific models of computation. The first uses binary variables and is the conservative-logic counterpart of switching theory; this model proves that universal computing capabilities are compatible with the reversibility and conservation constraints. The second model, which is a refinement of the first, constitutes a substantial breakthrough in establishing a correspondence between computation and physics. In fact, this model is based on elastic collisions of identical ``balls,'' and thus is formally identical with the atomic model that underlies the (classical) kinetic theory of perfect gases. Quite literally, the functional behavior of a general-purpose digital computer can be reproduced by a perfect gas placed in a suitably shaped container and given appropriate initial conditions.", issn="1572-9575", doi="10.1007/BF01857727", url="https://doi.org/10.1007/BF01857727" } @article{Landauer1961, author = {Landauer, R.}, title = {Irreversibility and Heat Generation in the Computing Process}, journal = {IBM J. Res. Dev.}, issue_date = {July 1961}, volume = {5}, number = {3}, month = jul, year = {1961}, issn = {0018-8646}, pages = {183--191}, numpages = {9}, url = {http://dx.doi.org/10.1147/rd.53.0183}, doi = {10.1147/rd.53.0183}, acmid = {1661186}, publisher = {IBM Corp.}, address = {Riverton, NJ, USA}, } @article{Margolus1998, title = "The maximum speed of dynamical evolution", journal = "Physica D: Nonlinear Phenomena", volume = "120", number = "1", pages = "188 - 195", year = "1998", note = "Proceedings of the Fourth Workshop on Physics and Consumption", issn = "0167-2789", doi = "http://dx.doi.org/10.1016/S0167-2789(98)00054-2", url = "http://www.sciencedirect.com/science/article/pii/S0167278998000542", author = "Norman Margolus and Lev B. Levitin", } @Inbook{Brassard1998, author="Brassard, Gilles and H{\O}yer, Peter and Tapp, Alain", editor="Lucchesi, Cl{\'a}udio L. and Moura, Arnaldo V.", title="Quantum cryptanalysis of hash and claw-free functions", bookTitle="LATIN'98: Theoretical Informatics: Third Latin American Symposium Campinas, Brazil, April 20--24, 1998 Proceedings", year="1998", publisher="Springer Berlin Heidelberg", address="Berlin, Heidelberg", pages="163--169", abstract="We give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O(3{\textsurd}N/r) expected evaluations of the function, where N is the cardinality of the domain. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Further, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.", isbn="978-3-540-69715-2", doi="10.1007/BFb0054319", url="https://doi.org/10.1007/BFb0054319" } @Article{vanOorschot1999, author="van Oorschot, Paul C. and Wiener, Michael J.", title="Parallel Collision Search with Cryptanalytic Applications", journal="Journal of Cryptology", year="1999", month="Jan", day="01", volume="12", number="1", pages="1--28", abstract="A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions. General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple encryption. The practical significance of the technique is illustrated by giving the design for three {\$}10 million custom machines which could be built with current technology: one finds elliptic curve logarithms in GF(2155) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers only 17 more bits of security than single-DES.", issn="1432-1378", doi="10.1007/PL00003816", url="https://doi.org/10.1007/PL00003816" } @article{bernstein2009cost, title={Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete}, author={Bernstein, Daniel J}, journal={SHARCS’09 Special-purpose Hardware for Attacking Cryptographic Systems}, pages={105} } @inproceedings{beals2013efficient, title={Efficient distributed quantum computing}, author={Beals, Robert and Brierley, Stephen and Gray, Oliver and Harrow, Aram W and Kutin, Samuel and Linden, Noah and Shepherd, Dan and Stather, Mark}, booktitle={Proc. R. Soc. A}, volume={469}, number={2153}, pages={20120686}, year={2013}, organization={The Royal Society} } @article{giovannetti2008quantum, title={Quantum random access memory}, author={Giovannetti, Vittorio and Lloyd, Seth and Maccone, Lorenzo}, journal={Physical review letters}, volume={100}, number={16}, pages={160501}, year={2008}, publisher={APS} }